We propose a fast sequential algorithm for the fundamental problem ofestimating frequencies and amplitudes of a noisy mixture of sinusoids. Thealgorithm is a natural generalization of Orthogonal Matching Pursuit (OMP) tothe continuum using Newton refinements, and hence is termed Newtonized OMP(NOMP). Each iteration consists of two phases: detection of a new sinusoid, andsequential Newton refinements of the parameters of already detected sinusoids.The refinements play a critical role in two ways: (1) sidestepping thepotential basis mismatch from discretizing a continuous parameter space, (2)providing feedback for locally refining parameters estimated in previousiterations. We characterize convergence, and provide a Constant False AlarmRate (CFAR) based termination criterion. By benchmarking against the Cramer RaoBound, we show that NOMP achieves near-optimal performance under a variety ofconditions. We compare the performance of NOMP with classical algorithms suchas MUSIC and more recent Atomic norm Soft Thresholding (AST) and Lassoalgorithms, both in terms of frequency estimation accuracy and run time.
展开▼
